public class RecursionAlgo {


    // 阶乘
    static int factorial(int n) {

        if (n == 1)
            return 1;

        return n * factorial(n - 1);

    }

    // 斐波那契数列
    static int fabnacci(int n) {

        if (n == 1 || n == 2)
            return 1;

        return fabnacci(n - 1) + fabnacci(n - 2);
    }

    // 所有数位数字求和如整数1234，所有数位数字求和后为10
    static int numSum(int n) {

        if (n == 0)
            return 0;

        return n % 10 + numSum(n / 10);
    }

    // 回文
    static boolean palindrom(String str) {

        int len = str.length();

        if (len == 0)
            return true;

        if (str.charAt(0) != str.charAt(len - 1))
            return false;

        return palindrom(str.substring(1, len - 1));

    }

    // 全排列
    static void fullPermutation(String str, int index) {

        if (index == str.length())
            return;

        for (int i = 0; i < str.length(); i++) {

            if (i == index)
                continue;

            StringBuffer sb = new StringBuffer(str);
            sb.setCharAt(i, str.charAt(index));
            sb.setCharAt(index, str.charAt(i));

            System.out.println(sb.toString());

        }


        fullPermutation(str, ++index);

    }

    // 二分查找
    // 找到后返回索引位置，没有找到则返回-1
    static int binarySearch(int n, int[] array, int begin, int end) {


        int mid = (begin + end) / 2;

        if (array[mid] == n)
            return mid;

        if (begin == end)
            return -1;

//        System.out.println(begin + " : " + end);

        if (n > array[mid]) {
            return binarySearch(n, array, mid + 1, end);
        } else {
            return binarySearch(n, array, begin, mid - 1);
        }

    }


    // 汉诺塔
    static void hanoi(int n, char from, char to, char helper) {

        if (n == 1) {
            System.out.println(from + " -> " + to);

            return;
        }

        hanoi(n - 1, from, helper, to);
        System.out.println(from + " -> " + to);
        hanoi(n - 1, helper, to, from);
    }

    // 整数逆序 1234 -> 4321
    static void intInverse(int n, StringBuffer sb) {

        if (n == 0)
            return;

        intInverse(n / 10, sb.append(n % 10));


    }


    public static void main(String[] args) {

        StringBuffer stringBuffer = new StringBuffer();
        intInverse(1234, stringBuffer);
        System.out.println(Integer.valueOf(stringBuffer.toString()));

        hanoi(3, 'a', 'c', 'b');

        System.out.println(binarySearch(19, new int[]{1, 3, 5, 9, 14, 16}, 0, 5));

        fullPermutation("abcd", 0);

        System.out.println(palindrom("abdcba"));

        System.out.println(numSum(12345));

        System.out.println(factorial(3));

        System.out.println(fabnacci(8));

    }
}
